package de.pass.ch.dijkstra;

import java.util.LinkedList;

import de.pass.ch.assign.Assignment;
import de.pass.ch.assign.AssignmentFactory;
import de.pass.ch.datastr.BinaryHeap;
import de.pass.ch.datastr.IntArrayGrowable;
import de.pass.ch.datastr.PQueueNodeDynQuery;
import de.pass.ch.graph.Path;
import de.pass.ch.graph.SearchGraph;
import de.pass.ch.graph.edge.Edge;
import de.pass.ch.graph.node.CurrentNode;
import de.pass.ch.graph.node.INode;
import de.pass.ch.pt.IStreetProfile;
import de.pass.ch.util.Util;

import static de.pass.ch.util.Constants.SPECIAL_NODEID;

public class DijkstraSearchCH extends AbstractDijkstra<PQueueNodeDynQuery> {

	private boolean[] _finished;
	private int[] nodemapping;
	private IStreetProfile streetProfile;
	private AssignmentFactory assignFactory;
	private int optimizationMode;
	private LinkedList<Pair> _stallQueue;
	private boolean stallOnDemand = true;

	@SuppressWarnings("unchecked")
	public DijkstraSearchCH(SearchGraph graph, String nodeMapFile,
			IStreetProfile profile, AssignmentFactory factory, int mode) {

		super(graph, new IntArrayGrowable[2], new BinaryHeap[2]);

		_settledNodes[0] = new IntArrayGrowable(1500);
		_settledNodes[1] = new IntArrayGrowable(1500);

		_pqueue[0] = new BinaryHeap<PQueueNodeDynQuery>(3000,
				new PQueueNodeDynQuery());
		_pqueue[1] = new BinaryHeap<PQueueNodeDynQuery>(3000,
				new PQueueNodeDynQuery());

		_finished = new boolean[2];
		
		_stallQueue = new LinkedList<DijkstraSearchCH.Pair>();

		_searchDirections = 2;

		streetProfile = profile;
		assignFactory = factory;
		optimizationMode = mode;

		if (nodeMapFile != null)
			nodemapping = Util.deserializeIntArray(nodeMapFile);

	}

	/**
	 * Bidirectional search from a given node s to a given node t (and vice
	 * versa). Used by the bidirectional version of Dijkstra's algorithm and the
	 * multilevel query ("hwy search").
	 * 
	 * @param source
	 *            the source node; SPECIAL_NODEID means: ignore forward
	 *            direction
	 * @param target
	 *            the target node; SPECIAL_NODEID means: ignore backward
	 *            direction
	 * @return distance from s to t or "infinity" if s and t aren't connected
	 */
	public int bidirSearch(int source, int target) {
		assert (checkClean());

		source = nodemapping[source];
		target = nodemapping[target];

		int noOfNodes = _graph.noOfNodes();

		if (source >= noOfNodes) {
			Assignment[] ass = assignFactory.getAssignments(source, noOfNodes,
					streetProfile, optimizationMode);
			for (Assignment a : ass) {
				if (a.getDirection() == 0 || a.getDirection() == 1) {
					int e = insert(0, a.getWeight(), a.getAssignedID(),
							new PQueueNodeDynQuery());
					PQueueNodeDynQuery data = pqData(0, e);
					data.setStartNode();
				}
			}
		} else {
			insertStartNode(0, source);
		}

		if (target >= noOfNodes) {
			Assignment[] ass = assignFactory.getAssignments(target, noOfNodes,
					streetProfile, optimizationMode);
			for (Assignment a : ass) {
				if (a.getDirection() == 0 || a.getDirection() == 2) {
					int e = insert(1, a.getWeight(), a.getAssignedID(),
							new PQueueNodeDynQuery());
					PQueueNodeDynQuery data = pqData(1, e);
					data.setStartNode();
				}
			}
		} else {
			insertStartNode(1, target);
		}

		_upperBound = Integer.MAX_VALUE;

		// initialization of the hwy search
		_finished[0] = false;
		_finished[1] = false;

		CurrentNode u = new CurrentNode();
		int searchID = 0;
		boolean pqEmpty[] = { _pqueue[0].empty(), _pqueue[1].empty() };
		while (!(pqEmpty[0] && pqEmpty[1])) {

			// different strategies: "Which pqueue should be preferred ?"

			// if (_pqueue[1].min() < _pqueue[0].min())
			// searchID = 1;
			// else
			// searchID = 0;
			// if (((_pqueue[1].size() < _pqueue[0].size()) && (!pqEmpty[1]))
			// || pqEmpty[0])
			// searchID = 1;
			// else
			// searchID = 0;
			if (!pqEmpty[1 - searchID])
				searchID = 1 - searchID;

			// If one search direction is finished, always choose the other one.
			if (_finished[0])
				searchID = 1;
			if (_finished[1])
				searchID = 0;

			// If the chosen pqueue is empty, there is nothing to do.
			if (pqEmpty[searchID])
				break;

			deleteMin(searchID, u);

			// *** relaxEdges ***
			relaxEdges(searchID, u, -1);

			// Check a simple abort-on-success criterion.
			if (_pqueue[searchID].min() > _upperBound) {
				_finished[searchID] = true;
			}

			// Iff both search directions are finished, we may abort.
			if (_finished[0] && _finished[1])
				break;

			pqEmpty[searchID] = _pqueue[searchID].empty();
		}

		processUnsettledNodes(0);
		processUnsettledNodes(1);

		return _upperBound;
	}

	public Path pathTo(int target, int searchID, boolean forward) {

		if (_upperBound == Integer.MAX_VALUE) {
			return null;
		}

		if (searchID < 0) {
			// first part of the path from s to the intermediate node 'via'
			Path path1 = pathTo(_via, 0, true);

			// second part of the path from the intermediate node 'via' to t
			Path path2 = pathTo(_via, 1, false);

			path1.targetNode = path2.targetNode;

			// combine both parts
			for (int i = path2.edges.size() - 1; i >= 0; i--) {
				path1.edges.add(path2.edges.get(i));
			}

			// We have the path forwards.

			return path1;
		} else {
			Path path = new Path();
			// determine path backwards, starting with t
			while (true) {
				int index = isReached(searchID, target);
				if (index == 0) {
					return path;
				}
				// determine parent
				int parent = pqData(searchID, index).parentNode();
				if (parent == target) {
					if (searchID == 0) {
						path.startNode = parent;
					} else {
						path.targetNode = parent;
					}
					break;
				}
				target = parent;
				PQueueNodeDynQuery data = pqData(searchID, index);

				if (searchID == 0) {
					path.edges.add(0,
							_graph.edge(data.parentNode(), data.parentEdge()));
				} else {
					path.edges.add(_graph.edge(data.parentNode(),
							data.parentEdge()));
				}
			}
			return path;
		}
	}

	/**
	 * Relaxes all (relevant) edges of the given node for the given search
	 * direction.
	 */
	private void relaxEdges(int searchID, CurrentNode parent, int ignore) {

		if (ignore < 0)
			ignore = SPECIAL_NODEID;

		int parentDist = parent.dist;

		// first and last edge of the current node in the current level
		int firstEdge = _graph.firstLevelEdge(parent.nodeID);
		int lastEdge = _graph.lastEdge(parent.nodeID);

		for (parent.edgeID = firstEdge; parent.edgeID < lastEdge; parent.edgeID++) {
			Edge edge = _graph.edge(parent.nodeID, parent.edgeID);

			int vID = edge.getTarget();
			INode v = _graph.node(vID);

			int index = 0;

			if (stallOnDemand) {
				// try to wake up a node v that can start a stalling process
				index = isReached(searchID, v);
				// Node v has to be the endpoint of an edge (u,v) that
				// points into the opposite direction
				// (because then the edge (v,u) which is used in the stalling
				// process points into
				// the right direction).
				// Furthermore, v has to be reached.
				if (edge.isDirected((byte) (1 - searchID)) && index != 0) {
					PQueueNodeDynQuery data = pqData(searchID, index);
					boolean stalled = data.stalled();
					int vKey = stalled ? data.stallKey() : pqKey(searchID,
							index);
					int newKey = vKey + edge.getWeight();
					if (newKey < parentDist) { // check whether this node is
												// 'promising'
						stall((byte) searchID, parent.nodeID, newKey);
						assert (pqData(searchID, parent.index).stalled());
						return;
					}
				}
			}

			// if the current edge points to the wrong direction, ignore it
			if (!edge.isDirected((byte) searchID))
				continue;

			// the new distance from the source of the search to the target of
			// the edge
			int newDist = parentDist + edge.getWeight();

			// perform the pqueue operation (insert or decreaseKey)
			int e;
			index = isReached(searchID, v);
			if (index == 0) {
				// v has been unreached -> INSERT it
				e = insert(searchID, newDist, vID, new PQueueNodeDynQuery());
			} else {
				// v has been reached -> try to DECREASE its KEY
				e = decreaseKey(searchID, newDist, vID);
			}
			if (e != 0) {
				// if the pqueue operation/the relaxation of the edge was
				// successful
				PQueueNodeDynQuery data = pqData(searchID, e);
				// update the parent of the node v
				data.updateParent(parent.nodeID, parent.edgeID);
			}
		}
	}

	/**
	 * Performs a stalling process, implemented by a BFS.
	 * 
	 * @param searchID
	 *            the search direction (the direction of the stalling process is
	 *            equal to the search direction)
	 * @param u
	 *            the 'stalling node' that starts the stalling process
	 * @param key
	 *            the key of the stalling node
	 */
	void stall(byte searchID, int u, int key) {
		int index = isReached(searchID, u);
		assert (index > 0);
		PQueueNodeDynQuery data = pqData(searchID, index);
		data.stallKey(key);
		_stallQueue.add(new Pair(u, key));
		// if (deepStallOnDemand) stallParent(searchID, u, data, key);

		while (!_stallQueue.isEmpty()) {

			Pair curr = _stallQueue.pop();
			u = curr.key;
			key = curr.value;

			int lastEdge = _graph.lastEdge(u);
			for (int e = _graph.firstLevelEdge(u); e < lastEdge; e++) {
				Edge edge = _graph.edge(u, e);
				int v = edge.getTarget();

				// if the current edge points to the wrong direction, ignore it
				if (!edge.isDirected(searchID))
					continue;

				index = isReached(searchID, v);
				if (index != 0) {
					int newKey = key + edge.getWeight();
					if (newKey < pqKey(searchID, index)) { // shorter path
															// found?
						data = pqData(searchID, index);

						if (!data.stalled()) {
							data.stallKey(newKey);
							_stallQueue.add(new Pair(v, newKey));
							// if (deepStallOnDemand) stallParent(searchID, v,
							// data, newKey);
						}
					}
				}
			}
		}
	}

	/** Inserts the given node as start node of the specified search direction. */
	private void insertStartNode(int searchID, int nodeID) {
		int index = insert(searchID, 0, nodeID, new PQueueNodeDynQuery());
		PQueueNodeDynQuery data = pqData(searchID, index);
		data.setStartNode();
	}

	/** Clears the search in order to be able to start a new search. */
	public void clear() {

		processUnsettledNodes(0);

		clearNodeVector(0, 1500);

		_pqueue[0] = new BinaryHeap<PQueueNodeDynQuery>(3000,
				new PQueueNodeDynQuery());

		processUnsettledNodes(1);

		clearNodeVector(1, 1500);

		_pqueue[1] = new BinaryHeap<PQueueNodeDynQuery>(3000,
				new PQueueNodeDynQuery());
	}

	public class Pair {

		public int key;
		public int value;

		public Pair() {
			this(0, 0);
		}

		public Pair(int k, int v) {
			key = k;
			value = v;
		}

	}

}
